"""
题目:https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
    给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
    例如：
    给定二叉树 [3,9,20,null,null,15,7],

        3
    / \
    9  20
        /  \
    15   7
    返回锯齿形层序遍历如下：

    [
    [3],
    [20,9],
    [15,7]
    ]

思路：可以先按照102题二叉树的层序遍历解法，获取二叉树的每层的节点值，再按照层数的奇偶值来确定是否要倒序输出该层的节点值。
时间复杂度：O(n),n为二叉树的节点数
空间复杂度：O(n)

"""



# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self,root):
        res = []
        queue = []
        if root:
            queue.append(root)
        while queue:
            n = len(queue)
            level = []
            for i in range(n):
                node = queue[i]
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                level.append(node.val)
            res.append(level)
            del queue[:n]
            
        return res

    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = self.levelOrder(root)
        #print('levels:{}'.format(levels))
        res = []
        for i in range(len(levels)):
            if i % 2 == 0:
                res.append(levels[i])
            else:
                res.append(levels[i][::-1])
        return res
